存储器章节内容较多 , 分开存放

4.5 高速缓冲存储器Cache⭐

局部性原理

空间局部性：在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是邻近的

  • 经典的使用比如 数组

时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息

高速缓冲技术就是利用局部性原理，把程序中正在使用的部分数据存放在一个高速的、容
量较小的Cache中，使CPU的访存操作大多数针对Cache进行，从而提高程序的执行速度。

CPU速度快，主存速度慢，且每年CPU速度的提升比主存快，CPU和主存的速度差距越来越大，

但是CPU再快，没有主存数据的输入也只能空等，

故在CPU和主存之间设置一个缓存，其速度比主存快，容量比主存小，

利用的局部性原理，将必要的一块数据存进缓存，CPU需要数据时先访问缓存，

如果没有找到再去主存中读取，这种方式使得CPU的效率得到很大的提升。

4.5.1 Cache工作原理

1. 主存和缓存的编址

如图，缓存和主存的地址都分为两部分，其中两者的块内地址相等，块内地址的大小决定了块的大小，

比如块内地址为4位，并且编址方式为字节，则每块大小为16字节。另外，cache中还存在一个标记，用于标识当前cache块对应的主存块号。

2.命中和未命中

主存和缓存按块存储，块的大小相同，若缓存共有 C 块，主存共有 M 块，那么 M 远远大于 C，CPU在主存中申请数据，如果这一块数据已经在缓存中了，则直接从缓存中调入CPU，这称为命中，否则表示未命中。如果命中，说明主存块和缓存块之间建立了对应关系，用 标记记录与某缓存块建立了对应关系的 主存块号。

3.命中率

CPU 欲访问的信息在 Cache 中的 比率，设 Nc 表示通过cache完成存取的总次数，Nm 表示通过主存完成存取的总次数，h 定义为命中率，则：h=Nc/(Nc+Nm)

命中率H:CPU欲访问的信息已在Cache中的比率

命中率与 cache 的 容量 与 块长 有关。容量越大越容易命中。块如果太小，则装不下一条指令，需要多个块；块太大，则总块数太少，块的大小适中，命中率越高，一般每块可取 4 ~ 8 个字，块长取一个存取周期内从主存调出的信息长度。

4.Cache的访问效率

tc 表示命中时的cache访问时间， tm 表示未命中时的主存访问时间， 1−h 表示未命中率，则平均访问时间 ta=htc+(1−h)tm，若e表示访问效率，则：e=tc/ta，可以知道访问效率介于 ：tc/tm—1。

5. Cache 的基本结构

image-20221206174952699

CPU通过地址总线发送主存块号，由于Cache和主存的块内地址编号相同，可以直接转换。主存块号先经过主存Cache地址映射变换机构判断是否命中:

  • 如果命中则给出相应的Cache地址的块号，然后从Cache存储体中取数据通过数据总线送给CPU。
  • 如果未命中，则查看Cache是否已满：
    • 如果未满，则通过主存块号访问主存，将数据装入Cache，Cache和主存有一条直接通路。
    • 如果已满，则经过Cache替换机构，通过替换算法，判断是否替换Cache的数据，以及和谁替换。
    • 与此同时，主存将CPU所需的数据通过数据总线直接交给CPU

主存Cache地址映射变换机构：
地址映射用于判断主存的数据可以存入到哪些Cache块中，变换机构用于查找某个主存块号所对应的Cache地址块号。

4.5.2 Cache 的写回策略

为何要保持在Cache和主存中数据的一致？
因为Cache中的内容是主存块副本，当Cache中的内容被更新时，就存在Cache和主存如何保持一致的问题。

1.读操作

2.写策略

主要解决问题：Cache 和主存的一致性。

以下情况也会出现“Cache一致性问题”

  1. 当多个设备都允许访问主存时(Cache分主存分/O设备)
    例：I/O设备可直接读写主存时，如Cache中的内容被修改，
    则I/O设备读出的对应主存单元的内容无效：
    若I/O设备修改了主存单元内容，则对应Cache槽中的内容无效。
  2. 当多个CPU都带有各自的Cache而共享主存时
    例：某个CPU修改了自身Cache中的内容，则对应的主存单元和其他CPU中对应的Cache槽的内容都变为无效。

  • 全写法（Write – through）
    写操作时数据既写入Cache又写入主存

    维护了一致性，但降低了Cache的功效。

    写操作时间就是访问主存的时间，Cache块退出时，不需要对主存执行写操作，更新策略比较容易实现，

    缺点是：会造成Cache和内存数据的频繁信息交换，如不停进行求和。

  • 回写法（Write – back）
    命中Cache时，只把数据写入 Cache 而不写入主存，当 Cache 数据被替换出去时才写回主存

    减少访存次数，但存在不一致性的隐患。

    无法保证Cache和内存操作时间的一致性，在并行计算机（多个独立Cache和主存）中会出现问题。

  • 写分配法： 未命中Cache时，从主存调入块，然后写Cache。

  • 非写分配法：未命中Cache时，只写主存，不调入块。

一般使用 回写法 与 写分配法 搭配使用

3.多层次的Cache

  1. 指令Cache和数据Cache
    设置两个相互独立的Cache
    指令Cache**:专门存放指令 (支持CPU指令流水线)
    数据Cache:专门存放数据

  2. 多层次Cache结构
    片内Cache的容量受CPU芯片集成度的限制。
    设二级Cache方案：

    • 一级Cache(L1)在CPU芯片内，容量小；

    • 二级Cache(L2)在CPU芯片外，容量大。

      注意下图中的 L1 L2 L3

    两级Cache之间设有专用总线相连。

4.5.3 Cache-主存的地址映射

3.6.2 Cache-地址映射_哔哩哔哩_bilibili

主存中的块放到cache的哪个位置?

概览

1. 直接映射

对号入座 – 一 一对应

将主存的字块进行分区，每个分区的大小和cache的大小相同，主存的第j块字块只能放在cache的第i块中，i=jmodC，C为cache的块数。如主存储体中蓝色部分只能放在Cache中的蓝色部分。

CPU给出的主存地址由三部分组成：主存字块标记，Cache字块地址，字块内地址。

  • 主存字块标记就是主存的分区号
  • 分区内的块号就是cache字块地址
  • 字块内地址就是字块内的偏移地址，在Cache和主存中相同，不用处理

以第0块为例：由于cache中的第0块装的可能是主存中任意一个分区的第0块，所以需要比较主存字块标记和cache上的标记是否相同，如果相同则说明命中。

该方式的缺点是cache的利用率不高，可能会反复换出同一个cache字块而其他字块空闲。

2. 全相联映射

可以理解为 – 空位随意放 => 利用率比较高

我们首先通过一个位数来标记字块是否被使用(主存字块标记) , 然后主存中的字块随机来访问cache

Cache利用率高，只要Cache中有空余则就可以装入。

由于可以装入到任意的位置，所以要和Cache所有的块比较判断是否命中，比较次数多。

同时主存字块标记要存m位（即主存块号），比较的位数也多，时间慢，电路复杂。

3. 组相联映射

先分组 , 然后组内随意放

直接映射和全相联映射方式是两个极端，一个只能放在固定位置，一个可以放在所有位置，

各自的优缺点也很明显，组相连映射是一种中庸的思路。

首先将cache分为Q组，同时将主存进行分区，每个区的块数等于cache的组数，

每个区的第i块只能放在cache的第i组中，但是在组中的位置可以任意。

组相联映射的地址结构为

路数越大，即每组Cache行的数量越大，发生块冲突的概率越低，但相联比较电路也越复
杂。选定适当的数量，可使组相联映射的成本接近直接映射，而性能上仍接近全相联映射。

某一主存块 j 按模 Q 映射到缓存的第 i=jmodQ 组中的任一块，其中主存块第 j 块只能放在 特定的第 i 组中，属于直接映射的思想，而可以放在特定组中任意一块，属于全相连映射的思想。

主存地址的组成如图所示，在cache中查找时，先根据组地址（即j mod Q）找到cache对应的组，

然后通过若干个并行的比较器（个数由每组块数决定）比较主存字块标记（即主存的分区号），只要有一个命中则命中。

4.5.4 替换算法

3.6.4 Cache例题替换版_哔哩哔哩_bilibili

有了Cache后，大大提高了CPU的工作效率。但未命中时，仍需访存，并将主存块调入Cache，

如Cache对应块地址槽已被占，则产生替换问题。

替换算法目的：获得最高命中率，使C访存数据尽可能在Cache中。

以下算法简单了解即可

1.随机算法RAND

考试一般不考

随机地确定替换的Cache块。它的实现比较简单，但没有依据程序访问的局部性原理，故可能命中率较低。

2.先进先出算法FIFO⭐

选择最早调入的行进行替换。

  • 它比较容易实现，但没有根据访存的局部性原理，故不能提高Cache的命中率。可能会把一些需要经常使用的程序块（如循环程序）也作为最早进入Cache的块替换掉。

3.近期最少使用算法LRU⭐

依据程序访问的局部性原理选择近期内长久未访问过的存储行作为替换的行，平均命中率要比FIFO要高，是堆栈类算法。

  • LRU算法对每行设置一个计数器，Cache每命中一次，命中行计数器清0，而其他各行计
    数器均加1，需要替换时比较各特定行的计数值，将计数值最大的行换出。

LRU位：Cache每行增设一计数器，记录主存块被访问情况，当替换出去时，该计数器清零。

  • n路组相联设log2n位

Cache总容量 =行数每行多少位

引申

MySQL innoDB存储引擎 , 数据库中的缓冲池是通过LRU (最近最少使用)算法来进行管理的, 即最频繁使用的页在LRU列表的前端 , 而最少使用的页在LRU 列表的尾端 , 当缓冲池不能存放新读取到的页时, 将会首先释放LRU列表中尾端的页

4.最不经常使用算法LFU

这个算法结合操作系统课程来进行学习

将一段时间内被访问次数最少的存储行换出。

  • 每行也设置一个计数器，新行建立后从0开始计数，每访问一次，被访问的行计数器加1，需要替换时比较各特定行的计数值，将计数值最小的行换出。

4.6 虚拟存储器⭐

4.6.1 虚拟存储器的基本概念

是指主存/辅存层次的存储系统，借助于辅助存储器来扩大主存容量，辅助存储器对CPU而言是“虚拟的”

虚拟存储器是指一个大容量的存储逻辑模型，不是实际物理存储器。

  • 更关注于功能是什么 , 并不关注于功能的细节如何实现

功能

  • 用户给出一个地址, 叫做虚地址或者逻辑地址, 虚拟存储器需要给出该地址对应的数据

实现

  • 由辅助硬件将虚地址映射到主存当中的某个单元，主存单元地址称为实地址或物理地址，
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main()
{
    int a= 10;
    int*p=&a;
    cout << p;
    return 0;
}

比如上面的代码 , 我们输出变量 a 的地址, 其实就是一个虚地址

1、实地址与虚地址

虚拟空间与主存空间都被划分成同样大小的页，主存的页称为实页，虚存的页称为虚页。

  • 用户编制程序时使用的地址称为虚地址或逻辑地址，其对应的存储空间称为虚存空间或逻辑地址空间。
  • 而计算机物理内存的访问地址则称为实地地或物理地址，其对应的存储空间称为物理存储空间或主存空间。
  • 程序进行虚地址到实地址转换的过程称为程序的再定位，有静态和动态两种。

2、虚存的访问过程

虚存空间的用户程序按照虚地址编程并存放在辅存中。程序运行时，由地址变换机构依据当时分配给该程序的实地址空间把程序的一部分调入实存。每次访存时，首先判断该虚地址所对应的部分是否在实存中：

  • 如果是，则进行地址转换并用实地址访问主存；
  • 否则，按照某种算法将辅存中的部分程序调度进内存，再按同样的方法访问主存。

由此可见：

  • 每个程序的虚地址空间如果远大于实地址空间，则以提高存储容量为目的。
  • 虚地址空间如果远小于实地址空间，则以地址变换为目的。通常出现在多用户或多任务系统中：实存空间较大，而单个任务并不需要很大的地址空间，较小的虚存空间则可以缩短指令中地址字段的长度。

3、Cache与虚存的异同

从虚存的概念可以看出，主存-辅存的访问机制与Cache-主存的访问机制是类似的。这是由Cache存储器、主存和辅存构成的三级存储体系中的两个层次。Cache-主存是为了提高速度，主存-辅存则是为了扩容。

相同点：

  • 出发点：二者都是为了提高存储系统的性价比而构造的分层存储体系，都力图使存储系统的性能接近高速存储器，而价格和容量接近低速存储器。
  • 原理相同：利用了程序运行时的局部性原理把最近常用的信息块从相对慢速而大容量的存储器调入相对高速而小容量的存储器。

不同点：

  • 侧重点不同：Cache主要解决主存与CPU的速度差异问题；而就性能价格比的提高而言，虚存主要是解决存储容量问题，另外还包括存储管理、主存分配和存储保护等方面。
  • 数据通路不同：CPU与Cache和主存之间均有直接访问通路，Cache不命中时可直接访问主存；而虚存所依赖的辅存与CPU之间不存在直接的数据通路，当主存不命中时只能通过调入解决，CPU最终还是要访问主存。
  • 透明性不同：Cache的管理完全由硬件完成，对系统程序员和应用程序员均透明；而虚存管理由软件（操作系统）和硬件共同完成，由于软件的介入，虚存对实现存储管理的系统程序员不透明，而只对应用程序员透明（段式和段页式管理对应用程序员“半透明”）。透明：意思是计算机中存在，但是不需要了解的东西，会用即可。
  • 未命中时的损失不同：由于主存的存取时间是Cache的存取时间的5～10倍，而主存的存取速度通常比辅存的存取速度快成千上万倍，故主存未命中时系统的性能损失要远大于Cache未命中时的损失。

4、虚存机制要解决的关键问题

  • 调度问题：决定哪些程序和数据应被调入主存。
  • 地址映射问题：在访问主存时把虚地址变为主存物理地址（这一过程称为内地址变换）；在访问辅存时把虚地址变成辅存的物理地址（这一过程称为外地址变换），以便换页。此外还要解决主存分配、存储保护与程序重定位等问题。
  • 替换问题：决定哪些程序和数据应被调出主存。
  • 更新问题：确保主存与辅存的一致性。

在操作系统的控制下，硬件和系统软件为用户解决了上述问题，从而使应用程序的编程大大简化。

4.6.2 页式虚拟存储器⭐

1、页式虚存地址映射

虚拟空间与主存空间都被划分成同样大小的页，主存的页称为实页，虚存的页称为虚页。

页式虚拟存储系统中，虚地址空间被分成等长大小的页，称为逻辑页；主存空间也被分成同样大小的页，称为物理页。相应地，虚地址分为两个字段：高字段为逻辑页号，低字段为页内地址（偏移量）；实存地址也分两个字段：高字段为物理页号，低字段为页内地址。通过页表可以把虚地址（逻辑地址）转换成物理地址，过程如下图所示：

由于虚存地址空间可以很大，因而每个进程的页表有可能非常长。例如，如果一个进程的虚地址空间为2G字节，每页的大小为512字节，则总的虚页数为 231/29=222 。如此一来，页表本身就要占用大量内存，并且还是连续的空间，这好吗？这不好。于是，一些系统把页表存储在虚存中，因而页表本身也要进行分页。当一个进程运行时，其页表中一部分在主存中，另一部分则在辅存中保存。

另一些系统采用二级页表结构。每个进程有一个页目录表，其中的每个表项指向一个页表。因此，若页目录表的长度（表项数）是m,每个页表的最大长度（表项数）为n,则一个进程最多可以有m×n个页。

在页表长度较大的系统中，还可以采用反向页表（反置页表） 实现物理页号到逻辑页号的反向映射。页表中对应每一个物理页号有一个表项，表项的内容包含该物理页所对应的逻辑页号。访存时，通过逻辑页号在反向页表中逐一查找。如果找到匹配的页，则用表项中的物理页号取代逻辑页号；如果没有匹配表项，则说明该页不在主存中。这种方式的优点是页表所占空间大大缩小，但代价是需要对反向页表进行检索，查表的时间很长。有些系统通过散列（哈希）表加以改进，但需要解决地址冲突的问题，这在操作系统中得以完成。

2、转换后援缓冲器

由于页表通常在主存中，因而即使逻辑页已经在主存中，也至少要访问两次物理存储器才能实现一次访存，这将使虚拟存储器的存取时间加倍。为了避免对主存访问次数的增多，可以对页表本身实行二级缓存，把页表中的最活跃的部分存放在更高速的存储器中（局部性原理），组成快表。这个专用于页表缓存的高速存储部件通常称为转换后援缓冲器(TLB)。保存在主存中的完整页表则称为慢表。

3、内页表和外页表

页表是虚地址到主存物理地址的变换表，通常称为内页表。与内页表对应的还有外页表，用于虚地址与辅存地址之间的变换。当主存缺页时，调页操作首先要定位辅存，而外页表的结构与辅存的寻址机制密切相关。例如对磁盘而言，辅存地址包括磁盘机号、磁头号、磁道号和扇区号等。

4.6.3 段式虚拟存储器和段页式虚拟存储器

1、段式虚拟存储器：

段是按照程序的自然分界划分的长度可以动态改变的区域。通常，程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中，并且每个程序可以有多个相同类型的段。在段式虚拟存储系统中，虚地址由段号和段内地址（偏移量）组成。虚地址到实主存地址的变换通过段表实现。每个程序设置一个段表，段表的每一个表项对应一个段。每个表项至少包含下面三个字段：

  • 有效位：指明该段是否已经调入实存。
  • 段起址：指明在该段已经调入实存的情况下，该段在实存中的首地址。
  • 段长：记录该段的实际长度。设置段长字段的目的是为了保证访问某段的地址空间时，段内地址不会超出该段长度导致地址越界而破坏其他段。

段表本身也是一个段，可以存在辅存中，但一般是驻留在主存中。

2、段式虚拟存储器的特点

段式虚拟存储器有许多优点：

  • 段的逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享。
  • 段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间。

段式虚拟存储器也有一些缺点：

  • 因为段的长度不固定，主存空间分配比较麻烦。
  • 容易在段间留下许多外碎片，造成存储空间利用率降低。
  • 由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚地址和实地址的最低若干二进制位作为段内偏移量，并与段号进行直接拼接，必须用加法操作通过段起址与段内偏移量的求和运算求得物理地址。因此，段式存储管理比页式存储管理方式需要更多的硬件支持。

3、段页式虚拟存储器

段页式虚拟存储器是段式虚拟存储器和页式虚拟存储器的结合。实存被等分成页。每个程序则先按逻辑结构分段，每段再按照实存的页大小分页，程序按页进行调入和调出操作，但可按段进行编程、保护和共享。

假如计算机系统中只有一个基址寄存器，则基号可不要。多道程序切换时，由操作系统修改基址寄存器内容。实际上，上述每个段表和页表的表项中都应设置一个有效位。只有在有效位为1时才按照上述流程操作，否则需中断当前操作先进行建表或调页。可以看出，段页式虚拟存储器的缺点是在由虚地址向主存地址的映射过程中需要多次查表，因而实现复杂度较高。

4.7 只读存储器ROM

用来保存固定的信息, 刚开始是不能写的, 虽然现在能写了, 但是速度相比写的速度以及RAM , CPU还是慢很多

4.7.1.只读存储器(ROM)的特点

ROM和RAM都是支持随机存取的存储器，其中SRAM和DRAM均为易失性半导体存储
器。而ROM中一旦有了信息，就不能轻易改变，即使掉电也不会丢失，它在计算机系统中是只
供读出的存储器。ROM器件有两个显著的优点：

  1. 结构简单，所以位密度比可读写存储器的高。

  2. 具有非易失性，所以可靠性高。

    对比RAM的易失性

    image-20221204163038463

比如我们平时编辑的一些文件, 如果没有保存 , 电脑直接断电, 那么就会丢失, 这就是因为这时候的数据其实是在RAM 里面的 , 并没有写入到ROM

对于如今的个人PC机 , 通常RAM就是内存, ROM就是硬盘

4.7.2.ROM的类型

根据制造工艺的不同，ROM可分为掩模式只读存储器(MROM)、一次可编程只读存储器
(PROM)、可擦除可编程只读存储器(EPROM)、Flash存储器和**固态硬盘(**SSD)。

  1. 掩模式只读存储器
    MROM的内容由半导体制造厂按用户提出的要求在芯片的生产过程中直接写入，写入以后
    任何人都无法改变其内容。优点是可靠性高，集成度高，价格便宜：缺点是灵活性差。

  2. 一次可编程只读存储器

    POM是可以实现一次性编程的只读存储器。允许用户利用专门的设备（编程器）写入自己的程序，一旦写入，内容就无法改变。

  3. 可擦除可编程只读存储器
    EPROM不仅可以由用户利用编程器写入信息，而且可以对其内容进行多次改写。EPROM
    虽然既可读又可写，但它不能取代RAM,因为EPROM的编程次数有限，且写入时间过长。

  4. F1ash存储器
    Flash存储器是在EPROM与EPROM的基础上发展起来的，其主要特点是既可在不加电的
    情况下长期保存信息，又能在线进行快速擦除与重写。Flsh存储器既有EPROM的价格便宜、
    集成度高的优点，又有EPROM电可擦除重写的特点，且擦除重写的速度快。

  5. 固态硬盘(Solid State Drives,SSD)
    基于闪存的固态硬盘是用固态电子存储芯片阵列制成的硬盘，由控制单元和存储单元
    (Flash芯片)组成。保留了Flash存储器长期保存信息、快速擦除与重写的特性。对比传统硬盘
    也具有读写速度快、低功耗的特性，缺点是价格较高。